package com.cheung.leetcode.normal;

public class LC35 {

    public static int searchInsert(int[] nums, int target) {
        if (target < nums[0]) {
            return 0;
        }
        if (target > nums[nums.length - 1]) {
            return nums.length;
        }


        int low = 0;
        int high = nums.length - 1;

        while (low <= high) {
            int mid = (low + high) / 2;

            if (target == nums[mid]) {
                return mid;
            }

            if (target > nums[mid]) {
                low = mid + 1;
            }

            if (target < nums[mid]) {
                high = mid - 1;
            }
        }


        return high + 1;
    }


    public static void main(String[] args) {
        System.out.println(searchInsert(new int[]{1, 3, 5, 6}, 4));
    }
}
